package com.jlh.viewer.algorithm;

import java.io.UnsupportedEncodingException;
import java.lang.reflect.Array;

/**
 * Created by jlh
 * On 2017/3/15 0015.
 */
public class MHeap<T extends Comparable> {
    private T[] datas;
    private int store;
    public MHeap(int size){
        datas= (T[]) Array.newInstance(Comparable.class,size);
        store=0;
    }
    public boolean push (T d){
        if (datas.length>store){
            int k=store;
            datas[store++]=d;
            if (k>=1) {
                adjust2((k-1)/2);
            }
        }
        return false;
    }

    public T pop (){
        if (store>0){
            swap(0,store-1);
            store--;
            adjust(0);
            return datas[store];
        }
        return null;
    }

    private void adjust2(int parent){
        int l=parent*2+1;
        int r=parent*2+2;
        int index = parent;
        if (l<store&&datas[index].compareTo(datas[l])<0){
            index=l;
        }
        if (r<store&&datas[index].compareTo(datas[r])<0){
            index=r;
        }
        if (index!=parent){
            swap(parent,index);
            if (parent!=0)
                adjust((parent-1)/2);
        }
    }

    private void adjust (int parent){
        int l=parent*2+1;
        int r=parent*2+2;
        int index = parent;
        if (l<store&&datas[index].compareTo(datas[l])<0){
            index=l;
        }
        if (r<store&&datas[index].compareTo(datas[r])<0){
            index=r;
        }
        if (index!=parent){
            swap(parent,index);
            adjust(index);
        }

    }


    private void swap (int a,int b){
        T temp = datas[a];
        datas[a]=datas[b];
        datas[b]=temp;
    }

    public static void main(String[] args) {
        MHeap<Integer> mHeap = new MHeap<>(15);
        mHeap.push(5);
        mHeap.push(3);
        mHeap.push(6);
        mHeap.push(7);
        mHeap.push(2);
        mHeap.push(9);
        while (mHeap.store>0)
            System.out.println(mHeap.pop());
    }
}
